package com.example.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 77. 组合
 * 如果是一个集合求组合，就需要start  ，如果是多个集合求组合，就不需要start
 * <p>
 * 需要start位来遍历不同元素，一般要配合剪枝优化
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 4, k = 2
 * 输出：
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 * 示例 2：
 * <p>
 * 输入：n = 1, k = 1
 * 输出：[[1]]
 * <p>
 * 回溯模版
 * void backtracking(参数) {
 * if (终⽌条件){
 * 存放结果;
 * return;
 * }
 * for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）){
 * 处理节点;
 * backtracking(路径，选择列表); // 递归
 * 回溯，撤销处理结果
 * }
 * }
 * <p>
 * <p>
 * 思路： 因为控制的是输出n个大小的字符
 * 所以引入startIndex概念
 * 每次递归将startIndex+1
 * 如果path大小等于目标大小，则加入result
 */
public class Combinations {
    static List<List<Integer>> result = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    public static List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     *
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     * @param n          这个n就相当于其它组合的数组[1,,,n] ,在此就直接用i就是数组值，在其它题中旧钥匙nums[i]
     */
    private static void combineHelper(int n, int k, int startIndex) {
        //终止条件
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        //剪枝
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        System.out.println(Combinations.combine(4, 3));
    }
}

